package com.yaoli.ajob;

/**
 * Created by will on 2017/2/27.
 */
public class _204_CountPrimes {
    public static void main(String[] args) {
        getPrime2(2);
    }

    public static int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (notPrime[i] == false) {
                count++;
                for (int j = 2; i*j < n; j++) {
                    notPrime[i*j] = true;
                }
            }
        }

        return count;
    }

    public static int getPrime2(int n) {
        boolean notPrime [] = new boolean[n + 1];
        int count = 0;

        for(int i = 2 ; i <= n; i ++){
            if(!notPrime[i]){
                if(isPrime(i)){
                    count++;
                }
                for (int j = 2; j*i <= n; j ++) {
                    notPrime[j*i] = true;
                }
            }
        }

        return count;
    }

    public static boolean isPrime(int j){
        for(int i = 3; i < Math.sqrt(j); i++){
            if(j % i == 0){
                return false;
            }
        }

        return true;
    }

    public static int getPrime(int n){
        if(n == 0 || n== 1){
            return 0;
        }

        n = n - 1;

        int set [] = new int[n+1];
        set[0] = 1;
        set[1] = 1;
        //是质数 全部为0
        for(int i = 2 ; i <= n; i ++){
            if(set[i] == 1){
                continue;
            }

            int j = i;
            for(j = i + j; j <= n ; j = j + i){
                set[j] = 1;//排除掉所有的 倍数
            }
            if(i*i > n){
                break;
            }
        }

        int count = 0;
        for(int i = 2 ; i < set.length ;i ++){
            if(set[i] == 0){
                count ++;
            }
        }



        return count;
    }



}
